package main

func parent(ch int) int {
	return ch / 2
}

func leftChild(parent int) int {
	return parent * 2
}

func rightChild(parent int) int {
	return leftChild(parent) + 1
}

type BinaryHeap struct {
	size int
	data []int
}

func New() *BinaryHeap {
	return &BinaryHeap{
		size: 0,
		data: make([]int, 1),
	}
}

func (h *BinaryHeap) Len() int {
	return h.size
}

func (h *BinaryHeap) IsEmpty() bool {
	return h.size == 0
}

func (h *BinaryHeap) Push(val int) {
	h.data = append(h.data, val)
	h.size++
	h.moveUp(h.size)
}

func (h *BinaryHeap) moveUp(ch int) {
	for {
		p := parent(ch)
		if p <= 0 {
			break
		}

		if h.data[ch] > h.data[p] {
			h.data[ch], h.data[p] = h.data[p], h.data[ch]
		}
		ch = p
	}
}

func (h *BinaryHeap) Pop() int {
	var val int
	if h.size == 1 {
		val = h.data[h.size]
		h.data = h.data[:h.size]
		h.size--
	} else if h.size > 1 {
		h.data[1], h.data[h.size] = h.data[h.size], h.data[1]
		val = h.data[h.size]
		h.data = h.data[:h.size]
		h.size--
		h.moveDown(1)
	}

	return val
}

func (h *BinaryHeap) moveDown(p int) {
	for {
		lc := leftChild(p)
		if lc > h.size {
			break
		}

		mc := h.maxChild(p)
		if h.data[mc] > h.data[p] {
			h.data[p], h.data[mc] = h.data[mc], h.data[p]
		}
		p = mc
	}
}

func (h *BinaryHeap) maxChild(p int) int {
	lc, rc := leftChild(p), rightChild(p)
	if rc > h.size || h.data[lc] > h.data[rc] {
		return lc
	} else {
		return rc
	}
}

func (h *BinaryHeap) Top() int {
	var val int
	if !h.IsEmpty() {
		val = h.data[1]
	}

	return val
}
